package tree;

public class LinkedList<E extends Comparable<E>> {

	public static void main(String[] args) throws Exception {

		LinkedList<String> ls = new LinkedList<String>();


		ls.addLast("1");
		ls.addLast("2");
		ls.insertOrderly("a");
		ls.insertOrderly("b");
		ls.insertOrderly("c");
		ls.insertOrderly("e");
		ls.insertOrderly("d");
		ls.insertOrderly("y");
		ls.insertOrderly("x");
		//		ls.reverse();
		System.out.println(ls.traverseToString());

		System.out.println("y".compareTo("x"));
	}

	// internal class for linked list use
	public static class SinglyLinkedNode<E>{
		E item;
		SinglyLinkedNode<E> next;
		public SinglyLinkedNode(){}
		public SinglyLinkedNode(E item){
			this.item = item;
		}
	}
	// linkedlist implementation
	private SinglyLinkedNode<E> head = null;
	public LinkedList()
	{

	}

	public void addFirst(E item)
	{
		if(head == null)
		{
			head = new SinglyLinkedNode<E>(item);
		}
		else
		{
			SinglyLinkedNode<E> tmpFirst = head;
			head = new SinglyLinkedNode<E>(item);
			head.next = tmpFirst;
		}
	}
	public void addLast(E item)
	{
		if(head == null)
		{
			head = new SinglyLinkedNode<E>(item);
		}
		else
		{
			SinglyLinkedNode<E> cursor = head;
			while(cursor.next != null)
			{
				cursor = cursor.next;
			}
			cursor.next = new SinglyLinkedNode<E>(item);
		}
	}

	public void insertOrderly(E item)
	{
		if(head == null)
		{
			head = new SinglyLinkedNode<E>(item);
		}
		else
		{
			SinglyLinkedNode<E> cursor = head;
			SinglyLinkedNode<E> cursorLeft = head;
			
			while(cursor.next != null)
			{
				if(item.compareTo(cursor.item) < 0)
					break;
				cursorLeft = cursor;
				cursor = cursor.next;
			}
			{
				SinglyLinkedNode<E> left = cursorLeft;
				SinglyLinkedNode<E> right = cursor;
				SinglyLinkedNode<E> newNode = new SinglyLinkedNode<E>(item);
				left.next = newNode;
				newNode.next = right;
			}
		}
		System.out.println(this.traverseToString());
	}

	public String traverseToString()
	{
		StringBuilder result = new StringBuilder();
		if(head != null)
		{
			result.append(head.item);
		}
		SinglyLinkedNode<E> cursor = head;
		while(cursor.next != null)
		{
			cursor = cursor.next;
			result.append(cursor.item);
		}
		return result.toString();
	}

	// Reverse a linked list Time: O(n) Space: O(1)
	public void reverse()
	{
		SinglyLinkedNode<E> cursorNode = head;
		while(cursorNode.next != null)
		{
			SinglyLinkedNode<E> temp = head;
			head = cursorNode.next;
			cursorNode.next = head.next;
			head.next = temp;
		}
	}

}
